package lc20240529;


import lc20240526.ListNode;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字。
 * 返回已排序的链表 。
 * @date 2024/5/29 21:14
 */
public class RemoveDuplicateElementFromSortedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(3, new ListNode(3)))));

        ListNode newHead = deleteDuplicates(head);
        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head;
        ListNode q = p.next;

        ListNode dummy = new ListNode(0);

        ListNode prev = dummy;

        while (q != null) {
            //p和q比较
            if (p.val != q.val) {
                prev.next = p;
                prev = prev.next;
            } else {
                //找到连续相同节点后第一个不同的节点。
                while (q != null && p.val == q.val) {
                    q = q.next;
                }
                prev.next = q;
            }
            //使得p指向q，q指向q的下一个节点。因为是要删除所有重复的节点。
            p = q;
            if (q != null) {
                q = q.next;
            }
        }
        return dummy.next;
    }
}
